package cn.njupt.binarysearchtree;

import cn.njupt.binarysearchtree.printer.BinaryTreeInfo;
import cn.njupt.binarysearchtree.printer.BinaryTrees;

import java.util.LinkedList;
import java.util.Queue;

//二叉搜索树
public class BinarySearchTree<E> implements BinaryTreeInfo {
    private int size;

    private Node<E> root;
    private Comparator<E> comparator;



    static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        public boolean hasTwoChildren(){
            return left!=null && right!=null;
        }

    }

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node) node).right;
    }

    @Override
    public Object string(Object node) {
        return ((Node) node).element;
    }


    public boolean contains(E element) {
        return node(element)!=null;

    }

    public Node<E> getRoot(){
        return root;
    }

    public void clear() {
        root=null;
        size=0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    /**
     * 向二叉搜索树中添加节点
     * @param element
     */
    public void add(E element) {
        elementCheckIsNull(element);
        if (root == null) {
            this.root = new Node<E>(element, null);
            size++;
            return;
        }
        Node<E> cur = root;
        Node<E> parent = null;
        int cmp = 0;
        while (cur != null) {
            parent = cur;
            cmp = compare(cur.element, element);
            if (cmp > 0) {  //右子树
                cur = cur.left;
            } else if (cmp < 0) {//左子树
                cur = cur.right;
            } else {
                cur.element = element;
                return;
            }
        }
        Node<E> node = new Node<E>(element, parent);
        if (cmp > 0) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        size++;
    }

    public int compare(E e1, E e2) {
        if (comparator != null) {
            return this.comparator.compare(e1, e2);
        }
        return ((Comparable) e1).compareTo(e2);
    }

    public void elementCheckIsNull(E element) {
        if (element == null) {
            throw new IllegalArgumentException("传递的参数为空");
        }
    }

    public void remove(E element) {
        remove(node(element));
    }

    private void remove(Node<E> node) {
        if(node==null) return;

        if(node.hasTwoChildren()){
            Node<E> pre=getPreceNode(node);//得到前驱节点
            node.element=pre.element;
            //删除pre
            node=pre;
        }
        Node<E> replacement=node.left==null?node.right:node.left;
        if(replacement!=null){ //度为1
            //判断左子树还是右子树
            if(node.parent==null){
                root=replacement;
                replacement.parent=node.parent;
            }else if(node==node.parent.left){ //左子树
                node.parent.left=replacement;
                replacement.parent=node.parent;
            }else{  //右子树
                node.parent.right=replacement;
                replacement.parent=node.parent;
            }
        }else{ //度为0
            if(node.parent==null){
                root=null;
            }else if(node.parent.left==node){
                node.parent.left=null;
            }else{
                node.parent.right=null;
            }

        }
        size--;
    }


    public Node<E> node(E element){
        Node<E> node=root;
        while(node!=null){
            int cmp=compare(node.element,element);
            if(cmp==0)return node;
            if(cmp>0){ //说明应该往左子树查询
                node=node.left;
            }else{ //说明应该往右子树查询
                node=node.right;
            }
        }
        return null;
    }
    /**
     * 判断是否是一颗完全二叉树
     *
     * @param root
     * @return
     */
    public boolean isComplete(Node<E> root) {
        if (root == null) return false;
        boolean leaf = false;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node<E> curNode = queue.poll();
            Node<E> left = curNode.left;
            Node<E> right = curNode.right;
            if (leaf && (left != null || right != null)
                    || (left == null && right != null)) {
                return false;
            }
            if (left != null) {
                queue.add(left);
            }
            if (right != null) {
                queue.add(right);
            } else {
                leaf = true;
            }
        }
        return true;

    }

    /**
     * 前序遍历二叉树,访问者模式？
     */
    public void preOrderTraversal(Node<E> root,Visitor<E> visitor){
        if(root==null || visitor.stop)return;

        //访问者模式，让二叉树遍历遍历到什么节点停止
        if(visitor.stop)return ;

        visitor.stop=visitor.visit(root.element);

        preOrderTraversal(root.left,visitor);
        preOrderTraversal(root.right,visitor);

    }

    /**
     * 中序遍历二叉树
     */
    public void inOrderTraversal(Node<E> root){
        if(root==null)return;
        inOrderTraversal(root.left);
        System.out.println(root.element);
        inOrderTraversal(root.right);
    }

    /**
     * 后序遍历二叉树
     */
    public void postOrderTraversal(Node<E> root){
        if(root==null)return;
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.println(root.element);
    }

    /**
     * 层序遍历二叉树
     */
    public void levelOrderTraversal(Node<E> root){
        if(root==null)return;
        Queue<Node<E>> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node<E> curNode=queue.poll();
            System.out.println(curNode.element);
            if(curNode.left!=null){
                queue.offer(curNode.left);
            }
            if(curNode.right!=null){
                queue.offer(curNode.right);
            }
        }

    }


    /**
     * 得到某个节点的前驱节点
     * @param node
     * @return
     */
    public Node<E> getPreceNode(Node<E> node){
        if(node==null)return node;
        if(node.left!=null){
            return getRightNode(node.left);
        }else{
            Node<E> parent=node.parent;
            while(parent!=null && parent.right!=node){
                node=parent;
                parent=node.parent;
            }
            return parent;
        }
    }

    public Node<E> getRightNode(Node<E> node){
        while(node.right!=null){
            node=node.right;
        }
        return node;
    }



}
